package com.wujunshen.algorithm.leetcode.divide.conquer;

/**
 * @author frank woo(吴峻申) <br>
 *     email:<a href="mailto:frank_wjs@hotmail.com">frank_wjs@hotmail.com</a> <br>
 * @date 2022/7/25 21:11<br>
 */
public class 数组中的第K个最大元素 {
  private int index;

  public int findKthLargest(int[] nums, int k) {
    // 快速选择完毕后第k大数的索引
    index = k - 1;
    quickSort(nums, 0, nums.length - 1);
    return nums[index];
  }

  private void quickSort(int[] arr, int l, int r) {
    if (l == r) {
      return;
    }
    int pivot = l + (int) (Math.random() * (r - l + 1));
    swap(arr, pivot, r);
    int left = l - 1;
    int right = r;
    // l和left在循环中都会改变，需要保留l的值，复用一下变量pivot
    pivot = l;
    while (l < right) {
      if (arr[l] > arr[r]) {
        swap(arr, ++left, l++);
      } else if (arr[l] < arr[r]) {
        swap(arr, --right, l);
      } else {
        l++;
      }
    }
    swap(arr, right, r);
    // 划分完后left和right的位置参见之前的图，根据index与二者关系继续递归或结束
    if (index <= left) {
      quickSort(arr, pivot, left);
    } else if (index > right) {
      quickSort(arr, right + 1, r);
    }
  }

  private void swap(int[] nums, int a, int b) {
    if (a != b) {
      int temp = nums[b];
      nums[b] = nums[a];
      nums[a] = temp;
    }
  }
}
